import java.util.Arrays;
import java.util.Scanner;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 独影
 * Date: 2022-11-21
 * Time: 15:26
 */


public class method {

   //19.数组的排序（冒泡排序）
    //给定一个数组，让数组升序或者降序排序
   public static void main(String[] args) {

   }






    //18.检查数组的有序性
    //给定一个整形数组，判断是否为有序的（升序）
    public static void main18(String[] args) {
        int[] array = {11,12,13,14,11};
        boolean lay = isUp(array);
        System.out.println(lay);
    }

    public static boolean isUp(int[] array) {
        for (int i = 0; i < array.length -1; i++) {
            if(array[i] > array[i+1]) {
                return false;
            }
        }
        return true;
    }







    // 17.二分查找（针对有序数组）
    public static void main17(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8};
        System.out.println(binarySearch(arr, 7));
    }
    public static int binarySearch(int[] arr, int key) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if(arr[mid] > key) {
                left = mid - 1;
            } else if(arr[mid] < key) {
                left = mid + 1;
            }else {
                return mid;
            }
        }
        return -1;//没找到的情况
    }


    //16.查找数组中指定元素（顺序查找）
    public static void main16(String[] args) {
       int[] arr = {4,5,1,3,8,56,45};
        System.out.println(findNum(arr, 56));
    }
    public static int findNum(int[] arr, int key) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == key) {
                return i;
            }
        }
        return -1;//没有找到就返回-1，数组的下标不可能为-1
    }










    //15.熟悉java代码，求数组中元素的平均值
    public static void main15(String[] args) {
        int[] arr = {12,34,56,74,25};
        System.out.println(average(arr));
    }
    public static double average(int[] arr) {
        int sum = 0;
        for(int x : arr) {
            sum += x;
        }
        return (double)sum / (double)arr.length;
    }








    //14.熟悉Java代码，找数组中最大的元素
    public static void main14(String[] args) {
        int[] array = {123,43,67,89,6};
        System.out.println(maxNum(array));
    }
    public static int maxNum(int[] array) {
         if (array == null) return -1;
         if (array.length == 0) return -1;//这两行是业务上的处理

        int max = array[0];
        for (int i = 1; i < array.length; i++) {  //for循环是从1下标开始遍历
            if(max < array[i]) {
                max = array[i];
            }
        }
        return max;
    }







    //13.熟悉代码   将{1,2,3,4,5} 用函数转换成[1,2,3,4,5]
    public static String myToString(int[] array) {
        if(array == null) {//传空指针会报错
            return "null";
        }

       String str = "[";
        for (int i = 0; i < array.length; i++) {
            str = str + array[i];
            if (i != array.length-1) {
                str = str  + ",";
            }
        }
        str = str + "]";
        return str;
    }
    public static void main13(String[] args) {
        int[] array = {1,2,3,4,5};
        System.out.println(myToString(array));
    }






    //开始学方法的递归，方法自己调用自己的过程

    //12.打印数组
    public static void main12(String[] args) {
        int[] array = {1,2,3,4,5,6};
        printf(array);
    }
    public static void printf(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }










    //11.汉诺塔问题，1个盘子要移动1次，2个盘子要移动3次，3个移动7次。
    //公式是2的n次方-1
    /**
     * @param n      代表盘子的个数
     * @param pos1  盘子所在的起始位置
     * @param pos2  盘子的中转位置
     * @param pos3  盘子的结束位置
     */
    public static void hanio(int n, char pos1, char pos2, char pos3) {
        if(n==1) {
            move(pos1,pos3); //如果只有一个盘子直接从起始位置移动到结束位置
        }else {
            hanio(n-1,pos1,pos3,pos2); //n-1除了第一个盘子其他的pos1起始位置，pos3中转位置，因为最大的留在pos3
            move(pos1,pos3);
            hanio(n-1,pos2,pos1,pos3);//盘子在2上通过1移动到3
        }
    }


    public static void move(char pos1, char pos2) {
        System.out.print(pos1+" -> "+pos2+" ");
    }


    public static void main11(String[] args) {
        hanio(3,'A','B','C');//中转，结束位置各放上A，B，C
    }







    //10.递归实现青蛙跳台阶问题
    public static int frogJump(int n) {
        if(n == 1 || n == 2) {
            return n;//这个问题相当于一个斐波那契数列，前两项是1 2
        }
        return frogJump(n-1)+frogJump(n-2);
    }
   //循环的方法解决青蛙跳台阶
    public static int frogJump2(int n) {
        if(n == 1 || n ==  2) {
            return n;
        }
        int a1 = 1;
        int a2 = 2;
        int a3 = 0;
        for (int i = 3; i <= n; i++) {
            a3 = a1 + a2;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }





    //9.斐波那契数列最好用循环(迭代)写
    public static int fei2(int n) {
        if(n == 1 || n ==  2) {
            return 1;
        }
        int a1 = 1;
        int a2 = 1;
        int a3 = 0;
        for (int i = 3; i <= n; i++) {
            a3 = a1 + a2;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }

    //8.递归实现斐波那契数列
     public static int fei(int n) {
         if(n == 1 || n ==  2) {
             return 1;
         }else {
             return fei(n-1)+fei(n-2);
         }
     }


    public static void main8(String[] args) {

        System.out.println(fei(3));
        System.out.println(fei(5));
        System.out.println(fei(7));

    }






    //7递归实现， 1729的每一位相加1+7+2+9
    public static int mySum(int n) {
        if(n < 10) {
         return n;
        }else {
            return  mySum(n / 10) + n % 10;
        }
    }

    public static void main7(String[] args) {
        System.out.println(mySum(1729));
    }





    //6递归实现，顺序打印12345的每一位
    public static void myPrint(int n) {
        if(n < 10) {
            System.out.println(n % 10+ " ");
        }else {
            myPrint(n / 10);
            System.out.println(n % 10 + " ");
        }
    }

    public static void main6(String[] args) {
       myPrint(1234);
    }





    //5递归实现求1+2+3+4+5的和
    public static int sumAdd(int n) {
       if(n == 1) {
           return 1;
       }else {
           return n + sumAdd(n-1);
       }
    }

    public static void main5(String[] args) {
       Scanner scanner =new Scanner(System.in);
       int n = scanner.nextInt();
        System.out.println(sumAdd(n));
    }














    //4.求最大值
    //创建方法求两个数的最大值max2，随后再求一个3个数的最大值max3
    //要求：在max3函数中，调用max2函数，实现三个数的最大值计算
    public static int max2(int a, int b) {
        return a > b ? a : b;
    }
    public static int max3(int a, int b, int c) {

        //内层的max2函数的结果作为外层max2函数的参数
        return max2(max2(a, b), c);
    }

    public static void main4(String[] args) {
        System.out.println(max3(45, 56, 2));
    }




    //3.奇数放在偶数前面,调整后不关心大小顺序
    //left  right  代表下标
    public static void main3(String[] args) {
        int[] arr = {1,2,34,66,3,4,5,6,7,8,9};
        int left = 0;
        int right = arr.length-1;
        while(left < right) {
            while(left < right && arr[left] % 2 != 0) {
                left++;
            }

            while(left < right && arr[right] % 2 == 0) {
                right--;
            }
            int tmp = arr[left];
            arr[left]=arr[right];
            arr[right]=tmp;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }




    //2.有一组数组，只有一个数字是出现一次，其他是两次，请找出这个数字
    public static void main2(String[] args) {
        int[] arr = {1,2,3,4,5,4,3,2,1};//java中数组的定义方法int[]
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {  //.length求数组的长度
            sum= sum ^ arr[i];
        }
        System.out.println(sum);
    }





    /**
     *  求1-n的和
     *  函数名字要用小驼峰
     * @param n 输入一个数字
     * @return 求得和
     */

    public static int sunAdd(int n){
     int sum = 0;
        for (int i = 1; i <= 10; i++) {
            sum += i;
        }
        return  sum;
    }

    public static void main1(String[] args) {
       int ret = sunAdd(10);
        System.out.println(ret);
        int a = 0;
        System.out.println(ret);
        System.out.println(sunAdd(10));
    }
}
